package com.leetcode.algorithm.y22.todo;

import java.util.Arrays;

/**
 * 1073. 负二进制数相加
 * 
 * https://leetcode.cn/problems/adding-two-negabinary-numbers/
 * 
 * @author jie.deng
 *
 */
class Question1073Solution01 {

	public int[] addNegabinary(int[] arr1, int[] arr2) {
		int len1 = arr1.length;
		int len2 = arr2.length;
		int carry = 0;
		int len = Math.max(len1, len2);
		int[] arr = new int[len];
		for (int i = 1; i <= len; i++) {
			int i1 = (len1 >= i) ? arr1[len1 - i] : 0;
			int i2 = (len2 >= i) ? arr2[len2 - i] : 0;
			int sum = i1 + i2 - carry;
			if (sum == 0 || sum == 1) {
				arr[len - i] = sum;
				carry = 0;
			} else if (sum == -1) {
				arr[len - i] = 1;
				carry = 1;
			} else if (sum == 2) {
				arr[len - i] = 0;
				carry = 1;
			}
		}
		if (carry == 1) {
			int[] retArr = new int[len + 2];
			retArr[0] = 1;
			retArr[1] = 1;
			for (int i = 0; i < len; i++) {
				retArr[2 + i] = arr[i];
			}
			return retArr;
		} else {
			int zeroIdx = 0;
			while (zeroIdx < len - 1 && arr[zeroIdx] == 0) {
				zeroIdx++;
			}
			if (zeroIdx == 0) {
				return arr;
			} else {
				return Arrays.copyOfRange(arr, zeroIdx, len);
			}
		}
	}

}